/*
    今天盲写一下堆排序 —— 升序
    向下调整建大堆，堆顶是最大的数，堆顶和堆尾交换，则最大的数跑到最后了。
    然后把除最后一个数外的其他数继续向下调整成为新的大堆。
    然后重复操作。

    最后做下性能测试，比较插入排序和希尔排序和堆排序
    ——> 希尔排序和堆排序平分秋色
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 向下调整 —— 大堆
// 参数：我们有数组、数组大小、还需要 parent
// 注：parent 的所有子树必须已经是大堆
void AdjustDown(int *a, int size, int parent)
{
    int bigChild = parent * 2 + 1; // 先认为左孩子是大孩子

    while (bigChild < size) // 没有孩子了就不用比较了
    {
        if (a[bigChild + 1] > a[bigChild] && bigChild + 1 < size)
        {
            bigChild += 1;
        }
        if (a[bigChild] > a[parent])
        {
            int tmp = a[bigChild];
            a[bigChild] = a[parent];
            a[parent] = tmp;

            // 更新 parent 和 bigChild
            parent = bigChild;
            bigChild = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

// 打印数组
void PrintArray(int *a, int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

// 测试向下调整
void testAdjustDown()
{
    int arr[] = {2, 8, 7, 6, 5, 4, 3, 2, 1};
    int sz = sizeof(arr) / sizeof(arr[0]);
    PrintArray(arr, sz);
    AdjustDown(arr, sz, 0);
    PrintArray(arr, sz);
}

// 堆排序 —— 升序
void HeapSort(int *a, int size)
{
    // 1.把原数组 a 建为大堆
    for (int i = (size - 1 - 1) / 2; i >= 0; i--)
        AdjustDown(a, size, i);

    int end = size - 1; // 堆尾下标

    // 2.把最大的值放到最后，然后对除了最大的值之外的所有值进行向下调整
    while (end > 0)
    {
        // 2.1堆顶和堆尾交换
        int tmp = a[0];
        a[0] = a[end];
        a[end] = tmp;

        // 2.2向下调整
        AdjustDown(a, end, 0);

        // 2.3更新堆尾
        end--;
    }
}

// 测试堆排序
void testHeapSort()
{
    int arr[] = {10,9,7,6,4,3,2,2,-10,-5,-401,-2,51,553};
    int sz = sizeof(arr) / sizeof(arr[0]);
    PrintArray(arr, sz);
    HeapSort(arr, sz);
    PrintArray(arr, sz);
}

// 直接插入排序 —— 升序
void InsertSort(int *a, int n)
{
    int i = 0;
    for (i = 0; i < n - 1; i++)
    {
        int end = i; // 第一次，end为 0； 第二次 end为 1；...；最后一次end为 n-1-1
        int tmp = a[end + 1];
        while (end >= 0)
        {
            if (tmp < a[end])
            {
                a[end + 1] = a[end];
                end--;
            }
            else
                break;
        }
        a[end + 1] = tmp;
    }
}

// 希尔排序 —— 升序
void ShellSort(int *a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        // 更新gap
        gap = gap / 3 + 1;

        //-----------------以gap为间隔完成1次预排序--------------------//
        int i = 0;
        for (i = 0; i < n - gap; i++)
        {
            int end = i; // 第一次，end 为 0; 第二次，end为 1；...；最后一次end为 n-gap-1
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                    break;
            }
            a[end + gap] = tmp;
        }
        //-----------------以gap为间隔完成1次预排序--------------------//
    }
}

void test_speed()
{
    // clock()函数：返回的是一个时间，该时间除以CLOCKS_PER_SEC(其实就是1000000)得到的就是秒数
    // 常通过计算前后时间差来计算进程消耗的时间。

    // 给数组 a1, a2, a3 N个随机数。
    srand(time(0));
    const int N = 5000000 * 2;
    // 在我的腾讯云机器(centos7)上测试：排序100w个数据跑不太出来，因为O(N^2)之后是比较1w亿次
    // 10w个数据：nsertSort: 5.960000 秒；ShellSort: 0.020000 秒
    int *a1 = (int *)malloc(sizeof(int) * N);
    int *a2 = (int *)malloc(sizeof(int) * N);
    int *a3 = (int *)malloc(sizeof(int) * N);
    int i = 0;
    for (i = 0; i < N; ++i)
    {
        a1[i] = rand();
        a2[i] = a1[i];
        a3[i] = a1[i];
    }

    // 计算插入排序和希尔排序前后的时间差
    clock_t begin1 = clock();
    //InsertSort(a1, N);
    clock_t end1 = clock();

    clock_t begin2 = clock();
    ShellSort(a2, N);
    clock_t end2 = clock();

    clock_t begin3 = clock();
    HeapSort(a3, N);
    clock_t end3 = clock();

    // printf("InsertSort: %f 秒\n", ((float)(end1 - begin1)) / CLOCKS_PER_SEC);
    printf("ShellSort: %f 秒\n", ((float)(end2 - begin2)) / CLOCKS_PER_SEC);
    printf("HeapSort: %f 秒\n", ((float)(end3 - begin3)) / CLOCKS_PER_SEC);
}

int main()
{
    // testAdjustDown();
    testHeapSort();
    // test_speed();
    return 0;
}